Graph Theory
Q33.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?Q34.
The conic section that is obtained when a right circular cone is cut through a plane that is parallel to the side of the cone is called _____Q35.
An ordered n-tuple (d_{1}, d_{2} ,... , d_{n}) with d_{1}\geq d_{2} \geq ... \geq d_{n} is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2} ,... , d_{n} respectively. Which of the following 6-tuples is NOT graphic?Q36.
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,f):1\leqi\leq12, 1\leqj\leq12}. There is an edge between (a,b) and (c,d) if |a-c|\leq1 and |b-d| \leq1. The number of edges in the graph is ____.Q37.
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?